#include "SalesmanData.h"
#include "math.h"

#include <QFile>
#include <QXmlStreamWriter>
#include <QDomDocument>
#include <QTime>


SalesmanData::SalesmanData()
{

}

SalesmanData::SalesmanData(QString filePath, QString fileName)
{
    QByteArray array = readFromFile(filePath, fileName);

    QDomDocument document;
    document.setContent(array,false);

    QDomElement rootElement = document.documentElement();

    QString cityName;
    double coordX;
    double coordY;
    bool ok;
    bool ok2;

    QDomNode n = rootElement.firstChild();
    while(!n.isNull()) {
        QDomElement e = n.toElement(); // try to convert the node to an element.
        if(!e.isNull())
        {
            //qDebug() << qPrintable(e.tagName()) << endl; // the node really is an element.
            cityName = e.attribute("name");
            coordX = e.attribute("x").toDouble(&ok);
            coordY = e.attribute("y").toDouble(&ok2);

            if(!ok || !ok2)
                qWarning("XML - error during conversion");

            addCity(SalesmanCity(cityName, QPointF(coordX, coordY)));
        }
        n = n.nextSibling();
    }


}

SalesmanData::SalesmanData(const SalesmanData& other)
{
    distanceArr = other.distanceArr;
    cityList = other.cityList;
}

SalesmanData::~SalesmanData()
{
}

void SalesmanData::addCity(QVector<double> dist)
{
    for(int i=0;i<dist.size();++i)
    {
        distanceArr[i].append(dist.at(i));
    }

    dist.append(0.0);
    distanceArr.append(dist);
}

/*void SalesmanData::addCity(QString name, QString distStr)
{
    QVector<double> dist;

    QStringList distL = distStr.split(",");

    bool ok;
    for(int i=0;i<distL.size();++i)
    {
        dist.append(distL[i].toDouble(&ok));
        if(ok != true)
            qWarning("conversion error");
    }

    addCity(name, dist);
}*/

/*void SalesmanData::addCity(QString name, double coordX, double coordY)
{
    QVector<double> distanceVector;
    double distance;

    double diffX;
    double diffY;

    for(int i=0;i<coordinates.size();++i)
    {
        diffX = coordX - coordinates.at(i).first;
        diffX *= diffX;
        diffY = coordY - coordinates.at(i).second;
        diffY *= diffY;
        distance = sqrt(diffX + diffY);
        distanceVector.append(distance);
    }

    for(int i=0;i<distanceVector.size();++i)
        qDebug() << QString::number(distanceVector.at(i));
    qDebug() << endl;

    coordinates.append(QPair<double,double>(coordX, coordY));

    addCity(name, distanceVector);
}*/

void SalesmanData::addCity(SalesmanCity city)
{
    QVector<double> distanceVector;
    double distance;

    double diffX;
    double diffY;

    for(int i=0;i<cityList.size();++i)
    {
        diffX = city.getCoord().x() - cityList.at(i).getCoord().x();
        diffX *= diffX;
        diffY = city.getCoord().y() - cityList.at(i).getCoord().y();
        diffY *= diffY;
        distance = sqrt(diffX + diffY);
        distanceVector.append(distance);
    }

    /*for(int i=0;i<distanceVector.size();++i)
        qDebug() << QString::number(distanceVector.at(i));
    qDebug() << endl;*/

    cityList.append(city);
    addCity(distanceVector);
}

SalesmanCity SalesmanData::getCity(int index)
{
    return cityList.at(index);
}

int SalesmanData::size()
{
    if(cityList.size() != distanceArr.size())
        qFatal("wrong SalsmanData size");
    return cityList.size();
}

void SalesmanData::clear()
{
    distanceArr.clear();
    cityList.clear();
}

bool SalesmanData::saveToFile(QString filePath, QString fileName)
{
    QFile* file = new QFile (filePath + fileName);

    if ( !file->open(QIODevice::WriteOnly) )
        return false;

    file->write ( generateXML() );
    file->close ();

    return true;
}

QByteArray SalesmanData::readFromFile(QString filePath, QString fileName)
{
    QFile* file = new QFile (filePath + fileName);

    if ( !file->open(QIODevice::ReadOnly) )
        return false;

    QByteArray array;
    array = file->readAll();
    file->close ();

    return array;
}

QByteArray SalesmanData::generateXML()
{
    QByteArray array("");

    QXmlStreamWriter* xml = new QXmlStreamWriter(&array);
    xml->setAutoFormatting(true);
    xml->writeStartDocument();
    xml->writeStartElement("CitySet");

    for (int i=0;i<cityList.size();++i)
    {
        xml->writeStartElement("City");
        xml->writeAttribute("name", cityList.at(i).getName());
        xml->writeAttribute("x", QString::number(cityList.at(i).getCoord().x()));
        xml->writeAttribute( "y", QString::number(cityList.at(i).getCoord().y()));
        xml->writeEndElement();
    }

    //xml->writeEndElement();//City Set
    xml->writeEndDocument();
    delete xml;
    return array;
}

double SalesmanData::distance(int from, int to) const
{
    return distanceArr[from][to];
}

QVector<double> SalesmanData::getCityDistanceVector(int index) const
{
    return distanceArr.value(index);
}

SalesmanData& SalesmanData::operator=(const SalesmanData& other)
{
    distanceArr = other.distanceArr;
    cityList = other.cityList;

    return *this;
}

QDebug operator<<(QDebug dbg, const SalesmanData& data)
{
    dbg.nospace() << "\t\t";
    for(int i=0;i<data.cityList.size();++i)
    {
        dbg.nospace() << data.cityList.at(i).getName();
    }

    dbg.nospace() << endl;

    for(int i=0;i<data.distanceArr.size();++i)
    {
        dbg.nospace() << data.cityList.at(i).getName() << "\t";
        for(int j=0;j<data.distanceArr[i].size();++j)
        {
            dbg.nospace() << data.distanceArr[i][j] << ",\t";
        }
        dbg.nospace() << endl;
    }

    return dbg.maybeSpace();
}

// BRUTE FORCE

QList<int> SalesmanData::findBestSalesmanRouteBF()
{
    int cityNum = distanceArr[0].size();

    QList<int> vect;
    QList<int> bestRoute;
    double bestRouteLen = 0.0;
    int ind = 0;
    double routeLength;

    for(int i=0;i<cityNum;++i)
        vect.append(i+1);

    QTime timer;
    timer.start();

    while( !(vect = getNextPermutation(vect)).isEmpty() )
    {
        routeLength = 0.0;
        for(int i=0;i<cityNum-1;++i)
        {
            routeLength += distanceArr[vect.at(i)-1][vect.at(i+1)-1];
        }

        routeLength += distanceArr[vect.at(cityNum-1)-1][vect.at(0)-1];
        if(ind == 0 || routeLength < bestRouteLen)
        {
            bestRouteLen = routeLength;
            bestRoute = vect;
        }

        ++ind;
    }
    ind++;
    double timeElapsed =  timer.elapsed()/1000.0;

    qDebug() << "iterations: " << ind;
    qDebug() << "shortest route: " << bestRouteLen;
    qDebug() << "time: " << timeElapsed;
    qDebug() << "permutations per second: " << QString::number(ind/timeElapsed, 'f');

    QString str("");
    for(int i=0;i<bestRoute.size();++i)
        str += QString::number(bestRoute[i]) + ",";
    qDebug() << str;

    return bestRoute;
}

QList<int> SalesmanData::getNextPermutation(QList<int> lastPermutation)
{
    int j = lastPermutation.size()-2;
    while(j >= 0 && lastPermutation[j] >= lastPermutation[j+1])
        --j;
    //qDebug() << "j: " << j;
    if(j<0)
    {
        qDebug() << "getNextPermutation - not found";
        return QList<int>();
    }

    int l = lastPermutation.size()-1;
    while(l > j && lastPermutation[j] >= lastPermutation[l])
        --l;

    //qDebug() << "l: " << l;
    lastPermutation.swap(j,l);

    int r1 = j+1;
    int r2 = lastPermutation.size()-1;

    while(r1<r2)
    {
        lastPermutation.swap(r1,r2);
        ++r1;
        --r2;
    }
    return lastPermutation;
}
